package com.codewsq;

/*
 * 数组的查找-（线性查找、二分法查找）
 * */
public class 算法线性查找和二分法查找 {

    public static void main(String[] args) {

        String[] arr = new String[]{"AA", "BB", "CC", "DD", "EE", "FF", "HH", "GG"};


        // 线性查找
        // 查找变量dest的值在数组中的位置
        String dest = "RR";
        boolean isFlag = false;
        for (int i = 0; i < arr.length; i++) {
            if (dest.equals(arr[i])) {
                System.out.println("找到了指定的元素，位置为：" + i);
                isFlag = true;
                break;
            }
        }
        if (!isFlag) {
            System.out.println("很遗憾，在arr数组中没有找到dest对应的值！");
        }

        /*--------------------------------------------------------------------------------------*/
        /*
         * 二分法查找
         * 前提：数组是有序的，无论升序还是降序
         * */
        //                      0   1   2   3   4   5   6    7    8
        int[] nums = new int[]{12, 43, 54, 67, 84, 99, 325, 546, 876};

        int aims = 325; // 查找aims的在数组中的第几位
        int head = 0; // 开始位置
        int end = nums.length - 1; //结尾位置
        boolean yes = false;
        while (head <= end) { // 如果开始位置小于或等于头位置，就继续循环

            int middle = (end + head) / 2; // 二分查找，获取的中间位置是middle
            if (aims == nums[middle]) { // 如果当前中间位置的值等于目标值，则跳出循环，目标值位置就是当前中间位置
                System.out.println(aims + "在数组中的位置是：" + middle);
                yes = true;
                break;
            } else if (aims < nums[middle]) { // 如果目标值小于当前位置的值，将结尾位置改为当前位置或者当前位置-1（这里是升序数组，降序数组反之）
                end = middle - 1;
            } else if (aims > nums[middle]) { // 如果目标值大于当前位置的值，将开始位置改为当前位置或者当前位置+1（这里是升序数组，降序数组反之）
                head = middle + 1;
            }
        }
        if (!yes) {
            System.out.println("很遗憾，在num数组中没有找到aims对应的值！");
        }

    }
}
